package lecode;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 * 示例 1：
 *
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 */
public class 全排列46 {

    public static void main(String[] args) {
       int[] nums =  {1,2,3};
//        List<List<Integer>> permute = permute(nums);
        List<List<Integer>> lists = permute2(nums);
//        System.out.println(permute);
        System.out.println(lists);
    }

    /**
     * 回溯算法 （递归）
     *
     */
    public static List<List<Integer>> permute(int[] nums) {
        //数组转list
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> origins = Arrays.stream(nums).boxed().collect(Collectors.toList());
        //判断路径中是否出现过改元素了，小技巧
        HashMap<Integer, Boolean> hashtable = new HashMap<>();
        for (Integer origin : origins) {
            hashtable.put(origin, false);
        }
        backtracking(origins,result,hashtable,new ArrayList<>());
        return result;
    }

    /**
     * 递归
     * @param origins 原始数组
     * @param result 最终结果数组
     * @param hash   判断元素是否出现过
     * @param list   拼接的数组
     */
    public static void backtracking(List<Integer> origins, List<List<Integer>> result, HashMap<Integer,Boolean> hash,List<Integer> list) {
        //判断结束条件 如果拼接的数组=原始数组长度说明是一个有效数组
        if (list.size() == origins.size()) {
            /*这行代码创建了一个新的ArrayList对象，它是通过复制list中的元素来初始化的。
            后续对这个新的ArrayList对象进行修改（例如添加或删除元素），不会影响原始的list。因为它们是两个独立的对象，在内存中有不同的存储位置。*/
            result.add(new ArrayList<>(list));
            return;
        }
        for (Integer origin : origins) {
            //如果当前元素没有出现过
            if (!hash.get(origin)) {
                list.add(origin);
                hash.put(origin, true);
                //递归到下一层
                backtracking(origins, result, hash, list);
                list.remove(list.size() - 1);
                hash.put(origin, false);
            }
        }
    }



    /**
     * 方法二、用数组做标识
     *
     */
    static List<Integer> path = new ArrayList<>();
    static List<List<Integer>> res = new ArrayList<>();
    static boolean[] used; //0为false
    public static List<List<Integer>> permute2(int[] nums) {
        used = new boolean[nums.length];//使用标记数组，避免重复使用。以空间换时间
        System.out.println("used " + Arrays.toString(used));
        permuteHelper(nums);
        return res;
    }

    public static void permuteHelper(int[] nums) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length ; i++) {
            //if (path.contains(nums[i])) {  时间复杂度为O(n)
            //    continue;
            //}
            if (used[i]) {
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            permuteHelper(nums);
            path.remove(path.size()-1);
            used[i] = false;
        }
    }

}
